package com.sheng.leetcode.year2022.month12.day04;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/12/05
 * <p>
 * 1774. 最接近目标价格的甜点成本<p>
 * <p>
 * 你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：<p>
 * 必须选择 一种 冰激凌基料。<p>
 * 可以添加 一种或多种 配料，也可以不添加任何配料。<p>
 * 每种类型的配料 最多两份 。<p>
 * 给你以下三个输入：<p>
 * baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。<p>
 * toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。<p>
 * target ，一个整数，表示你制作甜点的目标价格。<p>
 * 你希望自己做的甜点总成本尽可能接近目标价格 target 。<p>
 * 返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。<p>
 * <p>
 * 示例 1：<p>
 * 输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10<p>
 * 输出：10<p>
 * 解释：考虑下面的方案组合（所有下标均从 0 开始）：<p>
 * - 选择 1 号基料：成本 7<p>
 * - 选择 1 份 0 号配料：成本 1 x 3 = 3<p>
 * - 选择 0 份 1 号配料：成本 0 x 4 = 0<p>
 * 总成本：7 + 3 + 0 = 10 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18<p>
 * 输出：17<p>
 * 解释：考虑下面的方案组合（所有下标均从 0 开始）：<p>
 * - 选择 1 号基料：成本 3<p>
 * - 选择 1 份 0 号配料：成本 1 x 4 = 4<p>
 * - 选择 2 份 1 号配料：成本 2 x 5 = 10<p>
 * - 选择 0 份 2 号配料：成本 0 x 100 = 0<p>
 * 总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。<p>
 * <p>
 * 示例 3：<p>
 * 输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9<p>
 * 输出：8<p>
 * 解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。<p>
 * <p>
 * 示例 4：<p>
 * 输入：baseCosts = [10], toppingCosts = [1], target = 1<p>
 * 输出：10<p>
 * 解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。<p>
 * <p>
 * 提示：<p>
 * n == baseCosts.length<p>
 * m == toppingCosts.length<p>
 * 1 <= n, m <= 10<p>
 * 1 <= baseCosts[i], toppingCosts[i] <= 10^4<p>
 * 1 <= target <= 10^4<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/closest-dessert-cost">1774. 最接近目标价格的甜点成本</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1774 {

    @Test
    public void test01() {
//        int[] baseCosts = {1, 7}, toppingCosts = {3, 4};
//        int target = 10;
//        int[] baseCosts = {2, 3}, toppingCosts = {4, 5, 100};
//        int target = 18;
//        int[] baseCosts = {3, 10}, toppingCosts = {2, 5};
//        int target = 9;
        int[] baseCosts = {10}, toppingCosts = {1};
        int target = 1;
        System.out.println(new Solution().closestCost(baseCosts, toppingCosts, target));
    }
}

class Solution {
    int ans;

    /**
     * @param baseCosts    冰激凌基料价格
     * @param toppingCosts 冰激凌配料价格
     * @param target       要制作甜点的目标价格
     * @return 最接近 target 的甜点成本中最低的一种
     */
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        // 获取基料中价格最低的作为初始值
        ans = Arrays.stream(baseCosts).min().getAsInt();
        int n = baseCosts.length;
        int m = toppingCosts.length;
        // 循环基料，通过回溯 dfs 计算成本
        for (int i = 0; i < n; i++) {
            dfs(toppingCosts, 0, baseCosts[i], target);
        }
        return ans;
    }

    /**
     * @param toppingCosts 配料
     * @param p            添加配料的索引，从 0 开始
     * @param curCost      基料价格加上部分配料价格之后的价格
     * @param target       目标价格
     */
    public void dfs(int[] toppingCosts, int p, int curCost, int target) {
        // 如果当前差值小余现有价格和目标价格间的差值，结束
        if (Math.abs(ans - target) < curCost - target) {
            return;
        } else if (Math.abs(ans - target) >= Math.abs(curCost - target)) {
            // 如果当前差值比之前计算的差值要小，那么将当前价格赋值给 ans
            if (Math.abs(ans - target) > Math.abs(curCost - target)) {
                ans = curCost;
            } else {
                // 相等时，将价格中小的那个赋值给 ans
                ans = Math.min(ans, curCost);
            }
        }
        // 配料已经循环结束时，结束
        if (p == toppingCosts.length) {
            return;
        }
        // 当前配条分为加两份、加一份和不添加分别进行 dfs
        dfs(toppingCosts, p + 1, curCost + toppingCosts[p] * 2, target);
        dfs(toppingCosts, p + 1, curCost + toppingCosts[p], target);
        dfs(toppingCosts, p + 1, curCost, target);
    }
}
